
//76.最小覆盖子串
class Solution {
    public:
        string minWindow(string s, string t) {
            //先通过map统计t总各个字符出现的次数，同时记录t中字符的种类
            unordered_map<char ,int> mm;
            for(auto e:t)
                mm[e]++;
    
            int n=s.size(),left=0,num=mm.size();  //num表示t中的字符种类，同于判断是否能更新答案
            int ansl=0,ansr=0,flag=0;   //使用flag来标记是否存在适合的字串
            //进行滑动窗口
            for(int right=0;right<n;right++)
            {
                if(mm.count(s[right]))
                {
                    mm[s[right]]--;
                    if(mm[s[right]]==0) num--;
                }
                while(num==0)
                {
                    if(ansr==0||ansr-ansl>right-left) 
                    {
                        flag=1;                 //此处采用ansl和ansr的方式来代替string ret
                                                //因为后面测试有很长的可能会出现超出内存限制
                        ansl=left,ansr=right;   
                    }
                    if(mm.count(s[left]))
                    {
                        if(mm[s[left]]==0) num++;
                        mm[s[left]]++;
                    }
                    left++;
                }
            }
            return flag==0?"":s.substr(ansl,ansr-ansl+1);
        }
    };